﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <vector>

using namespace std;

//盈利计划
class Solution
{
public:
    int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit)
    {
        const int MOD = 1e9 + 7;
        // dp[i][j][k]:表示前i个计划中成员不超过j，利润至少为k的计划的种数
        // 注意这里是利润至少为k，k - profit[k] >= 0 但是profit[k]可能比k要大,导致 k - profit[k] < 0也是满足条件的，此时数组就会越界，我们选择0位置的值
        int len = group.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));
        // 当没有任务的时候，我们的利润为 0 ，此时⽆论⼈数限制为多少，我们都能找到⼀个空集的⽅案。
        for (int j = 0; j <= n; j++) dp[0][j][0] = 1;
        for (int i = 1; i <= len; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                for (int k = 0; k <= m; k++)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= group[i - 1])
                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[i][j][k] %= MOD;
                }
            }
        }

        return dp[len][n][m];
    }
};

// 滚动数组进行优化
class Solution
{
public:
    int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit)
    {
        const int MOD = 1e9 + 7;
        // dp[i][j][k]:表示前i个计划中成员不超过j，利润至少为k的计划的种数
        // 注意这里是利润至少为k，k - profit[k] >= 0 但是profit[k]可能比k要大,导致 k - profit[k] < 0也是满足条件的，此时数组就会越界，我们选择0位置的值
        int len = group.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int j = 0; j <= n; j++) dp[j][0] = 1;
        for (int i = 1; i <= len; i++)
        {
            for (int j = n; j >= group[i - 1]; j--)
            {
                for (int k = m; k >= 0; k--)
                {
                    dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[j][k] %= MOD;
                }
            }
        }

        return dp[n][m];
    }
};

//组合总和IV
class Solution
{
public:
    int combinationSum4(vector<int>& nums, int target)
    {
        // dp[i]:表示和i,一共有多少中选择方案
        vector<double> dp(target + 1);
        // 和为0.不选即可，此时为一种方案
        dp[0] = 1;
        for (int i = 1; i <= target; i++)
            for (auto x : nums)
                if (x <= i)
                    dp[i] += dp[i - x];

        return dp[target];
    }
};

//不同的二叉搜索树
class Solution
{
public:
    int numTrees(int n)
    {
        // dp[i] 表⽰：当结点的数量为 i 个的时候，⼀共有多少颗 BST
        vector<int> dp(n + 1);
        // 空树也是二叉搜索树
        dp[0] = 1;
        // 让每一个节点都作为根节点
        // 左子树为1 i-1 右子树为i+1 j
        // 枚举节点的总数
        for (int i = 1; i <= n; i++)
            // 枚举每一个根节点
            for (int j = 1; j <= i; j++)
                dp[i] += dp[j - 1] * dp[i - j];

        return dp[n];
    }
};

//汉诺塔问题
class Solution
{
public:
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c)
    {
        int n = a.size();
        return dfs(a, b, c, n);
    }

    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
    {
        if (n == 1)
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        dfs(a, c, b, n - 1);
        c.push_back(a.back());
        a.pop_back();
        dfs(b, a, c, n - 1);
    }
};

//合并两个有序链表
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        return dfs(list1, list2);
    }
    ListNode* dfs(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        if (l1->val <= l2->val)
        {
            l1->next = dfs(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = dfs(l2->next, l1);
            return l2;
        }
    }
};
int main()
{
	return 0;
}